package Greedy;

import java.util.Arrays;

/**
 * @Author: LDeng
 * @Date: 2021-04-16 14:56
 */
public class CoinChange {
    public static void main(String[] args) {
        Integer[] faces={25,10,5,1};

       coinChange(faces,41);
    }

    static void coinChange(Integer[] faces,int money){
        Arrays.sort(faces);
        int coins=0;
        int index=faces.length-1;//最后一枚索引
        while(index>=0){
            while(money>=faces[index]){
                money-=faces[index];
                coins++;
            }
            index--;
        }
        System.out.println(coins);

    }

    static void coinChange1(Integer[] faces,int money){
        Arrays.sort(faces,(Integer f1,Integer f2)-> f2-f1);
        int coins=0;
        int i=0;
        while(i<faces.length){
            if(money<faces[i]){
                i++;
                continue;
            }
            System.out.println(faces[i]);
            money-=faces[i];
            coins++;
        }
        System.out.println(coins);
    }

    static void coinChange2(){
        int[] faces={25,10,5,1};
        Arrays.sort(faces);
        int money=41;
        int coins=0;
        for(int i=faces.length-1;i>=0;i--){
            if(money<faces[i]) {
                continue;//选下一种面值的硬币
            };
            System.out.println(faces[i]);
            money=money-faces[i];
            coins++;
            //还要再找这个面值的硬币
            i++;

        }
        System.out.println(coins);
    }

}
